package com.gitee.ed.arithmetic.leetcode.answer.answer_1_100.answer_1_10;

import com.gitee.ed.arithmetic.leetcode.solution.solution_1_100.solution_1_10.Solution5;

/**
 * 标准最佳方案用动态规划
 *
 * @author hongda.li
 */
public class Answer5 implements Solution5 {
    @Override
    public String longestPalindrome(String s) {
        int length = s.length();

        StringBuilder builder;

        String longestPalindrome = "";

        for (int i = 0; i < length; i++) {
            builder = new StringBuilder();

            for (int j = i; j < length; j++) {
                builder.append(s.charAt(j));

                // 如果是回文
                if (this.isPalindrome(builder.toString())) {
                    longestPalindrome = builder.length() > longestPalindrome.length()
                            ? builder.toString()
                            : longestPalindrome;
                }
            }
        }

        return longestPalindrome;
    }

    private boolean isPalindrome(String s) {
        int length = s.length();
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) != s.charAt(length - 1 - i)) {
                return false;
            }
            if (length % 2 == 1 && i == length / 2) {
                return true;
            }
            if (length % 2 == 0 && i == length / 2 - 1) {
                return true;
            }
        }
        return true;
    }
}
